package class09_排序总结链表相关面试题;

/**
 *
 * 1)不基于比较的排序,对样本数据有严格要求,不易改写
 * 2)基于比较的排序,只要规定好两个样本怎么比大小就可以直接复用
 * 3)基于比较的排序,时间复杂度的极限是O(N*logN)
 * 4)时间复杂度O(N*logN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的
 * 5)为了绝对的速度选快排(大量实验的结论)、为了省空间选堆排、为了稳定性选归并
 *
 *常见的坑
 * 1)归并排序的额外空间复杂度可以变成O(1),“归并排序内部缓存法”,但是将变得不再稳定
 * 2)“原地归并排序”是垃圾贴,会让时间复杂度变成O(N^2)
 * 3)快速排序稳定性改进,“01 stable sort”,但是会对样本数据要求更多
 *
 * 工程上对排序的改进
 * 1)稳定性的考虑 （排序算法是否是稳定的）
 * 2)充分利用O(N*logN)和O(N^2)排序各自的优势（O(N^2)小数据量可能快，常数时间比较小）
 *
 * 例子：给定一个数组,要求把奇数放左边，偶数放右边，时间复杂度O(N),空间复杂度O(1)?  01 stable sort
 *
 * 链表问题
 * 面试时链表解题的方法论
 * 1)对于笔试,不用太在乎空间复杂度,一切为了时间复杂度
 * 2)对于面试,时间复杂度依然放在第一位,但是一定要找到空间最省的方法
 *
 * 链表面试题常用数据结构和技巧
 * 1)使用容器(哈希表、数组等)
 * 2)快慢指针
 *

 *
 *
 *
 */
public class Summarize {
}
